/*
 * @lc app=leetcode.cn id=1745 lang=cpp
 *
 * [1745] 回文串分割 IV
 */

// @lc code=start
class Solution
{
public:
    unordered_set<int> hash0, hashn;
    int n;
    void extract(string &s, int i, int j)
    {
        while (i >= 0 && j < n && s[i] == s[j])
        {
            if (i == 0)
                hash0.insert(j);
            if (j == n - 1)
                hashn.insert(i);
            i--, j++;
        }
    }
    bool isCheck(string &s, int i, int j)
    {
        while (i >= 0 && j < n && s[i] == s[j])
        {
            if (hash0.count(i - 1) && hashn.count(j + 1))
                return true;
            i--, j++;
        }
        return false;
    }
    bool checkPartitioning(string s)
    {
        n = s.size();
        for (int i = 0; i < n; i++)
        {
            extract(s, i, i);
            extract(s, i, i + 1);
        }

        for (int i = 1; i < n - 1; i++)
        {
            if (isCheck(s, i, i) || isCheck(s, i, i + 1))
                return true;
        }

        return false;
    }
};
// @lc code=end
